package com.bwt.tree.threadedBinaryTree;

public class ThreadedBinaryTreeDemo {
	public static void main(String[] args) {
		// 中序线索化二叉树的功能
		BinaryTree binaryTree = new BinaryTree();
		HeroNode root = new HeroNode(1, "宋江");
		HeroNode node2 = new HeroNode(3, "吴用");
		HeroNode node3 = new HeroNode(6, "卢俊义");
		HeroNode node4 = new HeroNode(8, "林冲");
		HeroNode node5 = new HeroNode(10, "关胜");
		HeroNode node6 = new HeroNode(14, "孙二娘");
		root.setLeft(node2);
		root.setRight(node3);
		node2.setLeft(node4);
		node2.setRight(node5);
		node3.setLeft(node6);

		// 设置父节点
		node2.setParent(root);
		node3.setParent(root);
		node4.setParent(node2);
		node5.setParent(node2);
		node6.setParent(node3);
		binaryTree.setRoot(root);
		binaryTree.postfixThreadedNodes(root);

	/*	System.out.println(node5.getLeft()); // 3
		System.out.println(node5.getRight()); // 1
*/
		System.out.println("线索化遍历~~");
		binaryTree.postfixThreadedList();
	}

}

// 定义ThreadedBinaryTre 实现了线索化功能的二叉树
class BinaryTree {
	private HeroNode root;

	// 为了实现线索化, 需要创建要给当前节点线索化的前驱节点的指针
	// 在递归进行线索化时,  pre 总是保留前一个节点
	private HeroNode pre = null;

	public void setRoot(HeroNode root) {
		this.root = root;
	}


	/**
	 * 前序线索化二叉树
	 *
	 * @param node 当前要线索化的节点
	 */
	public void prefixThreadedNodes(HeroNode node) {
		if (node == null) {
			return;
		}
		if (node.getLeft() == null) {
			node.setLeft(pre);
			node.setLeftType(1);
		}
		if (pre != null && pre.getRight() == null) {
			pre.setRight(node);
			pre.setRightType(1);
		}
		pre = node;
		if (node.getLeftType() != 1) {
			prefixThreadedNodes(node.getLeft());
		}
		if (node.getRightType() != 1) {
			prefixThreadedNodes(node.getRight());
		}
	}

	/**
	 * 前序线索化遍历
	 *
	 * @param
	 */
	public void prefixThreadedList() {
		HeroNode node = root;
		if (node == null) {
			return;
		}
		while (node != null) {
			while (node.getLeftType() != 1) {
				System.out.println(node);
				node = node.getLeft();
			}
			System.out.println(node);
			node = node.getRight();
		}
	}


	// 对二叉树进行中序线索化的方法

	/**
	 * @param node 当前需要线索化的节点
	 */
	public void threadedNodes(HeroNode node) {
		if (node == null) {
			return;
		}

		/*1.先线索化我们的左子树
		 * 2.线索化当前节点
		 * 3.线索化右节点*/
		threadedNodes(node.getLeft());
		// 处理当前节点的前驱节点
		if (node.getLeft() == null) {
			// 让当前节点的左指针指向前驱节点
			node.setLeft(pre);
			node.setLeftType(1);
		}
		// 处理后继节点
		if (pre != null && pre.getRight() == null) {
			// 让前驱节点的右指针指向当前节点
			pre.setRight(node);
			pre.setRightType(1);
		}
		// !!! 没处理一个节点后, 让当前节点是下一节点的前驱节点
		pre = node;

		threadedNodes(node.getRight());

	}

	// 线索化遍历二叉树的方法
	public void threadedList() {
		// 定义一个变量,用于存储当前遍历的节点,从root开始
		HeroNode node = root;
		while (node != null) {
			// 循环的找到leftType==1的节点, 第一个找到就是8节点
			// 后面随着遍历而变化,因为当lefttyoe==1时, 说明该节点时按照线索化处理后的有效节点
			while (node.getLeftType() == 0) {
				node = node.getLeft();
			}
			// 打印当前节点
			System.out.println(node);
			// 如果当前结点的右指针指向的是后继结点,则会一直输出
			while (node.getRightType() == 1) {
				node = node.getRight();
				System.out.println(node);
			}
			// 替换这个遍历节点
			node = node.getRight();
		}
	}

	public void postfixThreadedNodes(HeroNode node) {
		if (node == null) {
			return;
		}
		postfixThreadedNodes(node.getLeft());
		postfixThreadedNodes(node.getRight());
		if (node.getLeft() == null) {
			node.setLeft(pre);
			node.setLeftType(1);
		}
		if (pre != null && pre.getRight() == null) {
			pre.setRightType(1);
			pre.setRight(node);
		}
		pre = node;
	}

	public void postfixThreadedList() {
		pre = null;
		HeroNode node = root;
		// 找到前驱节点类型等于1的最左边的节点 应该是8 , 因为它是后序遍历的起点
		while (node != null && node.getLeftType() != 1) {
			node = node.getLeft();
		}
		while (node != null) {
			if (node.getLeftType() == 1 || node.getRightType()==1) {
				System.out.println(node);
				pre = node;
				node = node.getRight();
			} else {
				if (node.getRight() == pre) {
					System.out.println(node);
					pre = node;
					node = node.getParent();
				} else {
					node = node.getRight();
					while (node!=null&&node.getLeftType()==0&&node.getLeft()!=null) {
						node = node.getLeft();
					}
				}
			}
		}
	}
}


class HeroNode {
	private int no;
	private String name;
	private HeroNode left; // 默认null
	private HeroNode right; // 默认null
	private HeroNode parent;// 节点的父节点

	// 如果 leftType == 0 表示指向的是左子树, 如果是1 则表示指向前驱节点
	private int leftType;

	// rightType == 0 表示指向是右子树, 1 表示后继节点
	private int rightType;

	public HeroNode(int no, String name) {
		this.no = no;
		this.name = name;
	}

	public int getNo() {
		return no;
	}

	public void setNo(int no) {
		this.no = no;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public HeroNode getLeft() {
		return left;
	}

	public void setLeft(HeroNode left) {
		this.left = left;
	}

	public HeroNode getRight() {
		return right;
	}

	public void setRight(HeroNode right) {
		this.right = right;
	}


	public int getLeftType() {
		return leftType;
	}

	public void setLeftType(int leftType) {
		this.leftType = leftType;
	}

	public int getRightType() {
		return rightType;
	}

	public void setRightType(int rightType) {
		this.rightType = rightType;
	}

	public HeroNode getParent() {
		return parent;
	}

	public void setParent(HeroNode parent) {
		this.parent = parent;
	}

	@Override
	public String toString() {
		return "HeroNode{" +
				"no=" + no +
				", name='" + name + '\'' +
				'}';
	}
}

